Scientific visualization helps users better understand the large quantities of data with which they are dealing. These visualizations are typically computed on a large super computers and are sent to user workstations for viewing over a high speed network. One powerful technique for visualization is the use of motion to augment a user's understanding of the data. By creating animations which show various surfaces of the data being viewed and displaying them as a smooth motion sequence, more information about the data being studied can be conveyed.
As the user's display resolution increases, it is increasingly difficult to send enough data over the network to provide the smooth motion required. Even with a high bandwidth communication network, transmitting enough data for smooth motion (30 frames per second or higher) is difficult without the use of some form of compression and decompression. If each pixel is represented by 24 bits, such that each 8 bit byte represents a color, then it can be shown that the data throughput required to show motion is T=3H.sub.res V.sub.res F.sub.ref bytes per second, where T is throughput in bytes per second, H.sub.res is the horizontal resolution, or number of pixels per scanline, V.sub.res is the vertical resolution, or number of scanlines per frame, and F.sub.ref is the frame rate.
In order to support the high bandwidth for real-time motion video, it is necessary to have a very high bandwidth communication network. One such network is HPPI (High Performance Parallel Interface). HPPI is designed to support a maximum data rate of 100 million bytes per second with a 32-bit wide data bus. However, the bandwidth of even HPPI may not be enough for high resolution, real-time, smooth motion images. For example, in order to show a full scale image on a 2048.times.1536 high resolution display monitor using a 32 bit wide HPPI bus, the maximum frame rate achievable is, ##EQU1## where T.sub.hppi is the 100,000,000 bytes per second throughput on HPPI
With only 10.6 frames per second, any considerable motion of an object is rendered jerky. One way to achieve smoother motion is to use a communication network with an even higher bandwidth. However, such a high bandwidth communication network is expensive. It may not justify the cost/performance ratio for most users. An alternate way of achieving real-time motion image communication is incorporating an image compression/decompression technique.
An advantage of using compression and decompression of images is that the storage required to record the image sequence at the source is reduced. A graphics server may generate a movie sequence, but store only the compressed image data. This allows the use of the super computer DASD (i.e. disk) storage as a digital video recorder of substantially more image frames than is possible otherwise. Another advantage of compression/decompression is that the bandwidth required to transfer images is reduced.
A favored compression algorithm is the block truncation method that is described in detail by Healy et al. in "Digital Video Bandwidth Compression Using Truncation Coding", IEEE Trans. Comm., COM-9, Dec. 1981, pp. 1809-1823. It provides high quality text and graphic image decompression and reasonable quality television-like natural images. The compression method itself is not directly relevant to this invention and only certain aspects of it will be reviewed.
The basic idea of the algorithm is to represent each 4 by 4 region of pixels (48 bytes, assuming 3 bytes per pixel) by two colors (6 bytes) plus a 16-bit wide MASK. The two colors are calculated statistically to best represent the distribution of colors in the 4.times.4 pixel region. The two colors are called HI color and LO color. Each MASK bit determines whether the corresponding pixel should get either a HI or LO color. When the MASK is `1`, then the corresponding pixel gets the HI color; and when it is `0`then the corresponding pixel gets the LO color. This is illustrated in FIG. 1, which shows the bit mapping of a 4.times.4 pixel region 20 to its MASK 22. Since 4.times.4 pixels can be represented by using HI and LO colors (3 bytes each) and a 16 bit MASK (2 bytes), the compression ratio is R.sub.cmp =48/(3+3+2)=6.
The decompression mechanism is simpler than that of compression. For each 4.times.4 pixel matrix, a destination device receives two colors (HI and LO) and a 16 bit MASK. For each bit of the MASK, the corresponding pixel in the 4.times.4 pixel matrix gets either the HI color, if the MASK bit is `1`or the LO color if the MASK bit is `0`. FIG. 2 shows the compressed data format of an arbitrary 4.times.4 pixel area 24, where each pixel is either one of the two colors, A or B.
In a typical system, data received over the network is temporarily buffered into a FIFO store (first-in, first-out) until it is ready to be stored in a frame buffer. A preferred frame buffer is comprised of video random access memories (VRAM's). Such VRAM's are operated in the fast page mode where a memory cycle is typically 50 nS.
It is known that decompression can be done by storing the compressed data format into a frame buffer and then decompressing the pixel data at the time of video refresh. Another method is to decompress an image prior to storing it into the frame buffer. Although the first method requires less frame buffer memory than the second, it presents problems because the compressed pixel data format cannot easily be used for data manipulation and almost any such operation requires the pixel data to be decompressed first. Also, if the frame buffer stores only a compressed data format, then another frame buffer is needed to store uncompressed images. The solution is to decompress the data prior to storing it into the frame buffer, such that the frame buffer contains only a R, G, B pixel format.
There are a number of problems associated with decompression. The first is that the decompression must be done in real-time in order for the frame buffer not to be the bottleneck in the system. For example, for the HPPI bus, a transmission of 4.times.4 pixel compressed data takes nominally 80 nS. In order for the frame buffer not to be a bottleneck it must be able to perform the decompression in 80 nS per compressed data set. The decompression should be done in a cost-effective way, using parts that are available off-the-shelf.
A classical solution that improves a memory's bandwidth is to interleave the memory. There are two ways to interleave a memory. One is to access the interleaved memory in parallel such that, in one memory access time, there will be N operations for an N way interleaved memory. The second is to access interleaved memory in a time-serial overlapped manner, such that another memory access to a different module can be started 1/N memory cycle period later for an N-way interleaved memory.
In either case, the frame buffer should be designed such that the decompression bandwidth is greater than or equal to the communication network bandwidth so that the frame buffer is not the bottleneck of the system. In order to maximize the bandwidth, each memory module should have an independent data path and separate controls such that all modules can operate in parallel. Notice that as described before, in case of HPPI communication network, 16 pixels of information is transferred every 80 nS (16 pixels/50 nS=200 million pixels/seconds). If 50 nS bandwidth memory chips are used within the memory modules, then N must be at least 10 (10 pixels/50 nS=200 million pixels/second). If N is 16, then a maximum bandwidth of 320 million pixels per second can be achieved (16 pixels/50 nS). Although simple memory interleaving gives the best performance, it does not justify the complexity and cost of having multiple memory modules, each with its own separate data path and controls.
The second problem is that there must be access to the frame buffer from a local workstation. Furthermore, this access must be either in non-compressed mode or compressed mode. Non-compressed mode access is important if the decompressed data is used by the local workstation for image manipulation. The compressed mode access also allows an increase in performance of the local workstation.
The third problem is that for a high resolution monitor, the serial output of the VRAMs must be interleaved to provide the bandwidth necessary for that monitor. Since current VRAMs have serial output bandwidths of approximately 33 Mhz, a typical frame buffer design has serial output ports interleaved depending on the attached display. For example, for a monitor resolution of 1280.times.1024, the video bandwidth is 110 Mhz. Thus, four way VRAM serial output interleaving is sufficient for such resolution. However, for a monitor resolution of 2048.times.1536, the video bandwidth is 260 Mhz. This requires eight-way interleaving, since four way interleaving only gives 4.times.33 Mhz, or 132 Mhz, but 8 ways gives 264 Mhz. The frame buffer design and the decompression design should be able to provide flexible video output bandwidth such that the design is not limited to a monitor's resolution.
The prior art shows a variety of image compression/decompression schemes.
In U.S. Pat. No. 4,857,992, issued Aug. 15, 1989, entitled "Image Display Apparatus and Method" to Richards there is described a hardware compression/decompression mechanism in which an image is characterized by two sets of digital data. The first set of data is achieved by low-pass filtering the original image and then by sub-sampling of it. The second set of data is a delta pulse-code modulated set between the interpolated image of the first set and the original image. These two sets of data are compressed using run length coding techniques.
In U.S. Pat. No. 4,975,771, issued Dec. 4, 1990, entitled "Method And Apparatus For TV Broadcasting" to Kassatly there is described a method in which multiple channels of video can be broadcast on a single channel carrier by compressing the video data and then time-multiplexing as packets on the broadcast medium. Basically, this patent shows how a video signal carrier can be used more efficiently by transmitting multiple channel video on a single carrier.
In U.S. Pat. No. 4,970,663, issued Nov. 13, 1990 entitled "Method and Apparatus For Manipulating Digital Video Data" to Bedell et al. there is described a method for improving image quality by using a compression method in which 15 bit red, green, blue source image data is sub-sampled and then converted into 8-bit LUV luminance and chroma values. On a display, the LUV format data is expanded to a full resolution using a dithering technique.
In U.S. Pat. No. 4,797,729, issued Jan. 10, 1989 entitled "System Incorporating An Error Tolerant Picture Compression Algorithm" to Tsai, there is described a method of compression/decompression that is based on block truncation techniques. Decompression is accomplished serially through the use of multiplexers and registers. Both HI and LO color data are loaded into two registers, then the HI and LO data is chosen based on a bit MASK in pixel-serial order. The patent discloses the use of Y, I, Q color signal components and for the Y component, for instance, it requires 16 cycles to complete the decompression of a 4.times.4 set of pixels. Because of the serial nature of the decompression, its bandwidth is limited.
In U.S. Pat. No. 4,580,134, issued Apr. 1, 1986 entitled "Color Video System Using Data Compression and Decompression" to Campbell et al., there is described a system for encoding, transmitting, storing, and generating color images. This patent also uses block-truncation techniques wherein the compressed data blocks are stored into a block buffer memory. Then, the patent describes the use of "fast" serial decompression logic at the video output path. This system requires very sophisticated and expensive on-the-fly decoding circuitry to enable data transfer to a high performance graphics display. Furthermore, since the frame buffer only stores the compressed data format, it cannot be used to store non-compressed images. Since block truncation techniques employ a lossy compression/decompression method, a non-compressed mode is desirable when the quality of an image is the most important factor.
In U.S. Pat. No. 4,564,915, issued Jan. 14, 1986 entitled "YIQ Computer Graphics System" to Evans et al. there is described a computer graphics system that provides a color television raster scan video output. The architecture shown therein permits the frame buffer to be upgraded from a simple color map system to a RGB, full color resolution system but requires added memory storage.
In U.S. Pat. No. 4,541,010, issued Sep. 10, 1985 entitled "Electronic Imaging Camera" to Alston there is described an electronic camera utilizing a charge coupled device array as both an image sensing device and a buffer memory. A method is detailed in which a preview mode can be shown on a CRT monitor at a video rate without requiring another dedicated buffer.
An IBM Technical Disclosure Bulletin, August, 1985, pp. 958-959, to Asano describes an image compression/decompression scheme wherein image decompression occurs prior to storage in an image buffer. Subsequently, the stored image is mapped to an all-points-addressable memory for display in accordance with an accompanying command. Accordingly, it is an object of this invention to provide an improved display system which exhibits a frame buffer capable of real-time image decompression.
It is a further object of this invention to provide an improved display system wherein image decompression can be achieved on a real time basis for a high definition display image.
It is yet another object of this invention to provide an improved display system which is capable of employing off-the-shelf hardware, but yet exhibits substantially improved system performance characteristics.